/**
 * 343. 整数拆分
 * https://leetcode-cn.com/problems/integer-break/
 */
public class Solutions_343 {
    public static void main(String[] args) {
//        int n = 2;  // output: 1 * 2 = 1
        int n = 10;  // output: 3 * 3 * 4 = 36

        int result = integerBreak(n);
        System.out.println(result);
    }

    /**
     * 存在规律：
     * 要使拆分后正整数后，其乘积最大化，那么拆分的结果中，整数 3 需要最多
     * 所有的大于等于 4 的数，都可以拆分为 2 和 3 的组合
     * 相乘后，可以得到最大乘积
     */
    public static int integerBreak(int n) {
        int i = n / 3;
        int j = n % 3;
        if (n <= 3) {
            return n - 1;
        }
        if (j == 0) {
            // 3 * 3 * 3
            return (int) Math.pow(3, i);
        } else if (j == 1) {
            // (3 * 3 * 3 * 1) < (3 * 3 * 4)
            return (int) Math.pow(3, i - 1) * 4;
        } else if (j == 2) {
            // 3 * 3 * 3 * 2
            return (int) Math.pow(3, i) * 2;
        }
        return -1;
    }
}
